package graphmanip.collapsing;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Random;

import commonfunctions.Matrix;

/**
 * This class implements the Hungarian algorithm, an efficient algorithm for matching bipartite graphs.
 * 
 * @author Trevor Terris
 *
 */
public class HungarianAlgo {
	private boolean hasPrinted = false;
	private Matrix graph;
	public HungarianAlgo(Matrix m)
	{
		graph = m;
	}
	/**
	 * Takes the list of edges, returns the highest-weight bipartite matching
	 * 
	 * @param subgraph
	 * @return
	 */
	public ArrayList<Point> hungarianAlgorithm(ArrayList<Point> subgraph)
	{
		//first, creates the Matrix that determines the cost of going from one node to another
		ArrayList<Integer> from = new ArrayList<Integer>();
		ArrayList<Integer> to = new ArrayList<Integer>();
		for (int i = 0; i < subgraph.size(); i++)
		{
			int x = subgraph.get(i).x;
			int y = subgraph.get(i).y;
			if (!hasPrinted && (from.contains(y) || to.contains(x)))
			{
				System.out.println("A node is both a source and a sink, error might occur.");
				hasPrinted = true;
			}
			if (!from.contains(x))
				from.add(x);
			if (!to.contains(y))
				to.add(y);
		}
		
		//the Hungarian Algorithm only works with cost minimizing, so we subtract the actual
		//values from the maximum value.
		double maxVal = 0.0;
		for (int i = 0; i < subgraph.size(); i++)
		{
			double thisVal = graph.get(subgraph.get(i).x, subgraph.get(i).y);
			if (thisVal > maxVal)
				maxVal = thisVal;
		}
		
		Matrix weightMatrix = new Matrix(Math.max(from.size(), to.size()));
		
		for (int i = 0; i < weightMatrix.length(); i++)
		{
			for (int j = 0; j < weightMatrix.length(); j++)
			{
				if (j >= to.size() || i >= from.size() || 
						!subgraph.contains(new Point(from.get(i), to.get(j))))
					weightMatrix.set(maxVal, i, j);
				else 
					weightMatrix.set(maxVal - Math.max(0.0, graph.get(from.get(i), to.get(j))), i, j);
			}
		}
		
		int[] assignment;
		
		//subtracts the value of the smallest in the row from all elements in the row
		for (int i = 0; i < weightMatrix.length(); i++)
		{
			double minInRow = maxVal;
			for (int j = 0; j < weightMatrix.length(); j++)
			{
				double thisVal = weightMatrix.get(i, j);
				if (thisVal < minInRow)
					minInRow = thisVal;
			}
			for (int j = 0; j < weightMatrix.length(); j++)
				weightMatrix.set(weightMatrix.get(i, j) - minInRow, i, j);
		}
		//subtracts the value of the smallest in the column from all elements in the column
		for (int i = 0; i < weightMatrix.length(); i++)
		{
			double minInCol = maxVal;
			for (int j = 0; j < weightMatrix.length(); j++)
			{
				double thisVal = weightMatrix.get(j, i);
				if (thisVal < minInCol)
					minInCol = thisVal;
			}
			for (int j = 0; j < weightMatrix.length(); j++)
				weightMatrix.set(weightMatrix.get(j, i) - minInCol, j, i);
		}
		//repeats until a matching can be found. There are two points where the matching
		//is checked, so I used breaks instead of one check on the while loop.
		while (true)
		{
			//first it attempts to assign tasks, otherwise it comes up with the list of
			//unassigned values
			assignment = attemptToAssign(weightMatrix);
			boolean validAssignment = true;
			ArrayList<Integer> toIterateThrough = new ArrayList<Integer>();
			ArrayList<Integer> totalRows = new ArrayList<Integer>();
			ArrayList<Integer> totalCols = new ArrayList<Integer>();
			for (int i = 0; i < assignment.length; i++)
			{
				if (assignment[i] == -1)
				{
					validAssignment = false;
					toIterateThrough.add(i);
					totalRows.add(i);
				}
			}
			if (validAssignment)
				break;
			boolean addingCols = true;
			//if there isn't a matching yet, then it goes through and covers all the zeros by blocking off
			//some rows and some columns
			while(toIterateThrough.size() > 0)
			{
				ArrayList<Integer> nextToIterateThrough = new ArrayList<Integer>();
				for (int i = 0; i < toIterateThrough.size(); i++)
				{
					for(int j = 0; j < weightMatrix.length(); j++)
					{
						if(addingCols && weightMatrix.get(toIterateThrough.get(i), j) == 0.0 && !totalCols.contains(j))
						{
							totalCols.add(j);
							nextToIterateThrough.add(j);
						}
						else if(!addingCols && weightMatrix.get(j, toIterateThrough.get(i)) == 0.0 && !totalRows.contains(j))
						{
							if (assignment[j] == toIterateThrough.get(i))
							{
								totalRows.add(j);
								nextToIterateThrough.add(j);
							}
						}
					}
				}
				toIterateThrough = new ArrayList<Integer>(nextToIterateThrough);
				addingCols = !addingCols;
			}
			ArrayList<Integer> coveredCols = new ArrayList<Integer>(totalCols);
			ArrayList<Integer> coveredRows = new ArrayList<Integer>();
			for (int i = 0; i < weightMatrix.length(); i++)
			{
				if (!totalRows.contains(i))
					coveredRows.add(i);
			}
			//finds the minimum uncovered value
			double minVal = maxVal;
			for (int i = 0; i < weightMatrix.length(); i++)
			{
				for (int j = 0; j < weightMatrix.length(); j++)
				{
					if (!coveredRows.contains(i) && !coveredCols.contains(j) && minVal > weightMatrix.get(i, j))
						minVal = weightMatrix.get(i, j);
				}
			}
			//adds the value to areas where both the column and row are covered, subtracts it where
			//neither are covered
			for (int i = 0; i < weightMatrix.length(); i++)
			{
				for (int j = 0; j < weightMatrix.length(); j++)
				{
					if (coveredCols.contains(j) && coveredRows.contains(i))
						weightMatrix.set(weightMatrix.get(i, j) + minVal, i, j);
					if (!coveredRows.contains(i) && !coveredCols.contains(j))
						weightMatrix.set(weightMatrix.get(i, j) - minVal, i, j);
				}
			}
			//tries again to get a valid assignment
			assignment = attemptToAssign(weightMatrix);
			boolean isValid = true;
			for (int i = 0; i < assignment.length; i++)
			{
				if (assignment[i] == -1)
				{
					isValid = false;
					break;
				}
			}
			if (isValid)
				break;
		}
		ArrayList<Point> output = new ArrayList<Point>();
		
		//creates the output, the list of points, from the assignment array
		for (int i = 0; i < assignment.length; i++)
		{
			if (i < from.size() && assignment[i] < to.size() && 0.0 < graph.get(from.get(i), to.get(assignment[i])))
				output.add(new Point(from.get(i), to.get(assignment[i])));
		}
		return output;
	}
	/**
	 * This class attempts to assign the graph, given the matrix.
	 * 
	 * @param m
	 * @return
	 */
	private int[] attemptToAssign(Matrix m)
	{
		int[] toReturn = new int[m.length()];
		for (int i = 0; i < toReturn.length; i++)
			toReturn[i] = -1;
		
		int numUnassigned = toReturn.length;
		int lastNumUnassigned = 0;
		

		ArrayList<Integer> rowsAssigned = new ArrayList<Integer>();
		ArrayList<Integer> colsAssigned = new ArrayList<Integer>();

		//repeats this until there are no additional assignments
		do
		{
			int lastNumRows = -1;
			int lastNumCols = -1;
			lastNumUnassigned = 0;
			for (int i = 0; i < toReturn.length; i++)
			{
				if (toReturn[i] == -1)
					lastNumUnassigned++;
			}
			//first it tries to assign values that must be assigned, ie if there's a single zero
			//in a row or a column, then it must be assigned.
			while(rowsAssigned.size() > lastNumRows || colsAssigned.size() > lastNumCols)
			{
				lastNumRows = rowsAssigned.size();
				lastNumCols = colsAssigned.size();
				for (int i = 0; i < m.length(); i++)
				{
					if (!rowsAssigned.contains(i))
					{
						int indexOfZero = -1;
						boolean multipleZerosSeen = false;
						for (int j = 0; j < m.length(); j++)
						{
							if (!colsAssigned.contains(j) && m.get(i, j) == 0.0)
							{
								if (indexOfZero == -1)
									indexOfZero = j;
								else
									multipleZerosSeen = true;
							}
						}
						if (!multipleZerosSeen && indexOfZero != -1)
						{
							rowsAssigned.add(i);
							colsAssigned.add(indexOfZero);
							toReturn[i] = indexOfZero;
						}
					}
				}
				for (int i = 0; i < m.length(); i++)
				{
					if (!colsAssigned.contains(i))
					{
						int indexOfZero = -1;
						boolean multipleZerosSeen = false;
						for (int j = 0; j < m.length(); j++)
						{
							if (!rowsAssigned.contains(j) && m.get(j, i) == 0.0)
							{
								if (indexOfZero == -1)
									indexOfZero = j;
								else
									multipleZerosSeen = true;
							}
						}
						if (!multipleZerosSeen && indexOfZero != -1)
						{
							colsAssigned.add(i);
							rowsAssigned.add(indexOfZero);
							toReturn[indexOfZero] = i;
						}
					}
				}
			}
			//if all that must be assigned has been assigned, and the rest are ambiguous, then
			//it just assigns one of the ambiguous ones. After that, it checks if any will 
			//necessarily be assigned (so, it repeats)
			ArrayList<Integer> minValsToTry = new ArrayList<Integer>();
			int minIndex = 0;
			for (int i = 0; i < m.length(); i++)
			{
				ArrayList<Integer> valsToTry = new ArrayList<Integer>();
				if (!rowsAssigned.contains(i))
				{
					for (int j = 0; j < m.length(); j++)
					{
						if (!colsAssigned.contains(j) && m.get(i, j) == 0.0)
						{
							valsToTry.add(j);
						}
					}
				}
				if ((valsToTry.size() < minValsToTry.size() && valsToTry.size() > 0) || minValsToTry.size() == 0)
				{
					minValsToTry = valsToTry;
					minIndex = i;
				}
			}
			if (minValsToTry.size() != 0)
			{
				int toTry = minValsToTry.get((new Random()).nextInt(minValsToTry.size()));
				rowsAssigned.add(minIndex);
				colsAssigned.add(toTry);
				toReturn[minIndex] = toTry;
			}
			numUnassigned = 0;
			//repeats, unless there are no additional values assigned.
			for (int i = 0; i < toReturn.length; i++)
			{
				if (toReturn[i] == -1)
					numUnassigned++;
			}
			if (numUnassigned == 0)
				break;
		}while (lastNumUnassigned > numUnassigned);
		return toReturn;
	}
}
